package lanqiao;
/**
 * 数组切分【第十三届】【省赛】【B组】
 * [问题描述]
 * 已知一个长度为N的数组: A.A2.....A.v 恰好是1 ~N的一个排列。现在要求你将A数组切分成若干个(最少一个，最多N个)连续的子数组，并且
 * 每个子数组中包含的整数恰好可以组成一段连续的自然数。
 * 例如对于A= {1,3,2,4}, -共有5种切分方法:
 * {1}{3}{2}{4}:每个单独的数显然是(长度为1的)一段连续的自然数。
 * {1}{3,2}{4}: {3,2} 包含2到3，是- -段连续的自然数，另外{1}和{4}显然也是。
 * {1}{3,2,4}: {3,2,4}包含2到4, 是一段连续的自然数，另外{1}显然也是。.
 * {1,3,2}{4}: {1,3,2} 包含1到3，是一段连续的自然数，另外{4}显然也是。
 * {1,3,2,4}:只有一个子数组，包含1到4，是一段连续的自然数。
 * [输入格式]
 * 第一行包含一个整数N。第二行包含N个整数，代表A数组。
 * [输出格式]
 * 输出一个整数表示答案。由于答案可能很大，所以输出其对100000007取模后的值
 * 输入：
 * 4
 * 1 3 2 4
 * 输出：
 * 5
 */
import java.util.*;
public class Prev_13G {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] s = new int[n];
        for (int i = 0; i < s.length; i++) {
            s[i] = input.nextInt();
        }
        input.close();

        /** 动态规划 **/
        // 思路：
        // 第一时间想到的是回溯法，可以回溯出所有的切分方式，然后再判断合法的切分方式。
        // 但是这种做法时间复杂度更大，稍微长一点的数组其切分方式就会有很多。。
        // 所以可以想到使用动态规划，因为当你再次给数组后面添加一个元素时，你便可以在原结果上统计出新的结果，这就十分符合动态规划的逻辑。
        // 至于如何定义动规数组，怎么写状态转移方程；不应该像之前那样按死模板，而应该灵活，按自己的理解才能透彻的明白动态规划。。。

        // dp[i]表示截至到索引为i处的数组，有dp[i]种符合条件的切分方案
        int[] dp = new int[n];
        //初始化
        dp[0] = 1;
        //外层遍历索引截至位置
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1];
            //内层遍历包含索引为i的元素的切分方式
            for (int j = 0; j < i; j++) {
                //检验[j, i]区间是否符合条件
                int[] tmp = Arrays.copyOfRange(s, j, i+1);
                if(isLinkedNums(tmp)){
                    dp[i] += (j == 0 ? 1 : dp[j - 1]);
                    dp[i] %= 100000007;
                }
            }
        }
        System.out.println(dp[n - 1]);
    }

    //检验数组是否可以组成一段连续的自然数
    private static boolean isLinkedNums(int[] arr) {
        Arrays.sort(arr);
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] != arr[i-1] + 1){
                return false;
            }
        }
        return true;
    }
}

//切分方式
// 1 1 1 1 1 1 1+1+1=3 3+1+1=5 5 5+5=10 10 10 10 10+10=20 20 20+20=40  40 40 40+40=80 80+40+40=160
// 1 3 5 2 6 8 7       9       9 10     15 23 1  2        11 12        14 22 21       20
// 这就是动态规划的全过程。一定要理解相邻数据之间的关系。。。